#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int beautifulSubstrings(string s, int k) {
        int len = s.size();
        vector<int> v(len + 1);
        vector<int> c(len + 1);
        for (int i = 0; i < len; i++) {
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                v[i + 1] = v[i] + 1;
                c[i + 1] += c[i];
            }
            else {
                v[i + 1] += v[i];
                c[i + 1] = c[i] + 1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= len; i++) {
            for (int l = 0; l + i - 1 < len; l++) {
                int r = l + i - 1;
                int x = v[r + 1] - v[l];
                int y = c[r + 1] - c[l];
                if (x == y && (x * y) % k == 0)ans++;
            }
        }
        return ans;
    }
};